{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Time to Complete All Tasks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #greedy #array #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #贪心 #数组 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findMinimumTime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #完成所有任务的最少时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你有一台电脑，它可以 <strong>同时</strong>&nbsp;运行无数个任务。给你一个二维整数数组&nbsp;<code>tasks</code>&nbsp;，其中&nbsp;<code>tasks[i] = [start<sub>i</sub>, end<sub>i</sub>, duration<sub>i</sub>]</code>&nbsp;表示第&nbsp;<code>i</code>&nbsp;个任务需要在 <strong>闭区间</strong>&nbsp;时间段&nbsp;<code>[start<sub>i</sub>, end<sub>i</sub>]</code>&nbsp;内运行&nbsp;<code>duration<sub>i</sub></code>&nbsp;个整数时间点（但不需要连续）。</p>\n",
    "\n",
    "<p>当电脑需要运行任务时，你可以打开电脑，如果空闲时，你可以将电脑关闭。</p>\n",
    "\n",
    "<p>请你返回完成所有任务的情况下，电脑最少需要运行多少秒。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>tasks = [[2,3,1],[4,5,1],[1,5,2]]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>\n",
    "- 第一个任务在闭区间 [2, 2] 运行。\n",
    "- 第二个任务在闭区间 [5, 5] 运行。\n",
    "- 第三个任务在闭区间 [2, 2] 和 [5, 5] 运行。\n",
    "电脑总共运行 2 个整数时间点。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>tasks = [[1,3,2],[2,5,3],[5,6,2]]\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>\n",
    "- 第一个任务在闭区间 [2, 3] 运行\n",
    "- 第二个任务在闭区间 [2, 3] 和 [5, 5] 运行。\n",
    "- 第三个任务在闭区间 [5, 6] 运行。\n",
    "电脑总共运行 4 个整数时间点。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= tasks.length &lt;= 2000</code></li>\n",
    "\t<li><code>tasks[i].length == 3</code></li>\n",
    "\t<li><code>1 &lt;= start<sub>i</sub>, end<sub>i</sub> &lt;= 2000</code></li>\n",
    "\t<li><code>1 &lt;= duration<sub>i</sub> &lt;= end<sub>i</sub> - start<sub>i</sub> + 1 </code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-time-to-complete-all-tasks](https://leetcode.cn/problems/minimum-time-to-complete-all-tasks/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-time-to-complete-all-tasks](https://leetcode.cn/problems/minimum-time-to-complete-all-tasks/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[2,3,1],[4,5,1],[1,5,2]]', '[[1,3,2],[2,5,3],[5,6,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key = lambda x:x[1])\n",
    "        run = [False] * (tasks[-1][1] + 1)\n",
    "        for start, end, d in tasks:\n",
    "            d -= sum(run[start:end + 1])\n",
    "            if d > 0:\n",
    "                for i in range(end, start -1, -1):\n",
    "                    if run[i]:continue\n",
    "                    run[i] = True\n",
    "                    d -=1\n",
    "                    if d == 0:break\n",
    "        \n",
    "        return sum(run)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda t: t[1])\n",
    "        run = [False] * (tasks[-1][1] + 1)\n",
    "        for start, end, d in tasks:\n",
    "            d -= sum(run[start:end + 1])  # 去掉运行中的时间点\n",
    "            if d > 0:\n",
    "                for i in range(end, start - 1, -1):  # 剩余的 d 填充区间后缀\n",
    "                    if run[i]: continue\n",
    "                    run[i] = True\n",
    "                    d -= 1\n",
    "                    if d == 0: break\n",
    "        return sum(run)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda t: t[1])\n",
    "        run = [False] * (tasks[-1][1] + 1)\n",
    "        for start, end, d in tasks:\n",
    "            d -= sum(run[start:end + 1])  # 去掉运行中的时间点\n",
    "            if d > 0:\n",
    "                for i in range(end, start - 1, -1):  # 剩余的 d 填充区间后缀\n",
    "                    if run[i]: continue\n",
    "                    run[i] = True\n",
    "                    d -= 1\n",
    "                    if d == 0: break\n",
    "        return sum(run)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda t: t[1])\n",
    "        st = [(-2, -2, 0)]  # 闭区间左右端点，栈底到栈顶的区间长度的和\n",
    "        for start, end, d in tasks:\n",
    "            _, r, s = st[bisect_left(st, (start,)) - 1]\n",
    "            d -= st[-1][2] - s  # 去掉运行中的时间点\n",
    "            if start <= r:  # start 在区间 st[i] 内\n",
    "                d -= r - start + 1  # 去掉运行中的时间点\n",
    "            if d <= 0: continue\n",
    "            while end - st[-1][1] <= d:  # 剩余的 d 填充区间后缀\n",
    "                l, r, _ = st.pop()\n",
    "                d += r - l + 1  # 合并区间\n",
    "            st.append((end - d + 1, end, st[-1][2] + d))\n",
    "        return st[-1][2]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda t:t[1]) #对齐每组end位,便于找到最大长度\n",
    "        run=[False]*(tasks[-1][1]+1)\n",
    "        for s,e,d in tasks:\n",
    "            d-=sum(run[s:e+1])\n",
    "            for i in range(e,s-1,-1):\n",
    "                if run[i]: continue\n",
    "                if d<=0: break\n",
    "                run[i]=True\n",
    "                d-=1\n",
    "        return sum(run)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda t:t[1])\n",
    "        run = [0]*(tasks[-1][1]+1)\n",
    "        for s,e,d in tasks:\n",
    "            d-=sum(run[s:e+1])\n",
    "            if d>0:\n",
    "                for i in range(e,s-1,-1):\n",
    "                    if run[i]: continue\n",
    "                    run[i] = 1\n",
    "                    d-=1\n",
    "                    if d==0:break\n",
    "        return  sum(run)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda t: t[1])\n",
    "        run=[0]*(tasks[-1][1] + 1)\n",
    "        for task in tasks:\n",
    "            task[2]-=sum(run[task[0]:task[1]+1])\n",
    "            if task[2]>0:\n",
    "                for i in range(task[1],task[0]-1,-1):\n",
    "                    if run[i]==0:\n",
    "                        run[i]=1\n",
    "                        task[2]-=1\n",
    "                    if task[2]==0:\n",
    "                        break\n",
    "        return sum(run)\n",
    "                                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "\n",
    "        # 按照持续时间小的排序\n",
    "        tasks.sort(key=lambda x:(x[1]))\n",
    "\n",
    "        res=[0]*2020\n",
    "        for s,e,d in tasks:\n",
    "            d-=sum(res[s:e+1])\n",
    "            if d>0:\n",
    "                for i in range(e,s-1,-1):\n",
    "                    if res[i]==0:\n",
    "                        res[i]=1\n",
    "                        d-=1\n",
    "                    if d==0:break\n",
    "        return sum(res)\n",
    "            \n",
    "        \n",
    "        return res.count(1)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda t: t[1])\n",
    "        run = [False] * (tasks[-1][1] + 1)\n",
    "        for start, end, d in tasks:\n",
    "            d -= sum(run[start:end + 1])  # 去掉运行中的时间点\n",
    "            if d > 0:\n",
    "                for i in range(end, start - 1, -1):  # 剩余的 d 填充区间后缀\n",
    "                    if run[i]: \n",
    "                        continue\n",
    "                    run[i] = True\n",
    "                    d -= 1\n",
    "                    if d == 0: \n",
    "                        break\n",
    "        return sum(run)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda x: x[1])\n",
    "        ls = [0]*2002\n",
    "        for a,b,c in tasks:\n",
    "            d = sum(ls[a:b+1])\n",
    "            e = c -d \n",
    "            while e > 0 :\n",
    "                if ls[b] ==0:\n",
    "                    ls[b] =1\n",
    "                    e -=1\n",
    "                b -=1\n",
    "        return sum(ls) \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda x: x[1])\n",
    "        use = [False] * (tasks[-1][1] + 1)\n",
    "        for start, end, d in tasks:\n",
    "            d -= sum(use[start:end + 1])\n",
    "            if d > 0:\n",
    "                for t in range(end, start - 1, -1):\n",
    "                    if use[t]:continue\n",
    "                    use[t] += 1\n",
    "                    d -= 1\n",
    "                    if d == 0:\n",
    "                        break\n",
    "        return sum(use)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "\n",
    "        tasks.sort(key=lambda x: x[1])\n",
    "        time = [0] * (tasks[-1][1] + 1)\n",
    "        for l, r, d in tasks:\n",
    "            cur = sum(time[l:r + 1])\n",
    "            if cur < d:\n",
    "                left = d - cur\n",
    "                for t in range(r, l - 1, -1):\n",
    "                    if not time[t]:\n",
    "                        time[t] = 1\n",
    "                        left -= 1\n",
    "                        if not left:\n",
    "                            break\n",
    "        \n",
    "        return sum(time)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda t:t[1])\n",
    "        run=[False]*(tasks[-1][1]+1)\n",
    "        for s,e,d in tasks:\n",
    "            d-=sum(run[s:e+1])\n",
    "            if d>0:\n",
    "                for i in range(e,s-1,-1):\n",
    "                    if run[i]:\n",
    "                        continue\n",
    "                    run[i]=True\n",
    "                    d-=1\n",
    "                    if d==0:\n",
    "                        break\n",
    "        return sum(run)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef findMinimumTime(self, tasks):\n",
    "\t\ttasks.sort(key=lambda t: t[1])\n",
    "\t\trun = [False] * (tasks[-1][1] + 1)\n",
    "\t\tfor start, end, d in tasks:\n",
    "\t\t\td -= sum(run[start:end + 1])  # 去掉运行中的时间点\n",
    "\t\t\tif d > 0:\n",
    "\t\t\t\tfor i in range(end, start - 1, -1):  # 剩余的 d 填充区间后缀\n",
    "\t\t\t\t\tif run[i]: continue\n",
    "\t\t\t\t\trun[i] = True\n",
    "\t\t\t\t\td -= 1\n",
    "\t\t\t\t\tif d == 0: break\n",
    "\t\treturn sum(run)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda t: t[1])\n",
    "        run = [False] * (tasks[-1][1] + 1)\n",
    "        for start, end, d in tasks:\n",
    "            d -= sum(run[start:end + 1])  # 去掉运行中的时间点\n",
    "            if d > 0:\n",
    "                for i in range(end, start - 1, -1):  # 剩余的 d 填充区间后缀\n",
    "                    if run[i]: continue\n",
    "                    run[i] = True\n",
    "                    d -= 1\n",
    "                    if d == 0: break\n",
    "        return sum(run)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(reverse=True)\n",
    "        nums = [0] * len(tasks)\n",
    "        totalNums = [t[2] for t in tasks]\n",
    "        endArr = []\n",
    "        ans = 0\n",
    "        # [[2,3,1],[4,5,1],[1,5,2]]\n",
    "        for i in range(2005):\n",
    "            while tasks and tasks[-1][0] == i:\n",
    "                c = tasks.pop()\n",
    "                idx = len(tasks)\n",
    "                heapq.heappush(endArr, (c[1], idx, c[0]))\n",
    "            while endArr and endArr[0][0] == i:\n",
    "                c = heapq.heappop(endArr)\n",
    "                idx = c[1]\n",
    "                if totalNums[idx] - nums[idx] > 0:\n",
    "                    val = totalNums[idx] - nums[idx]\n",
    "                    ans += val\n",
    "                    nums[idx] += val\n",
    "                    for j in endArr:\n",
    "                        nums[j[1]] = min(i - j[2] + 1, nums[j[1]] + val)\n",
    "            if not tasks and not endArr: break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "    贪心： 暴力枚举右端点\n",
    "    1. 按照右端点排序\n",
    "    2. 对于 tasks[i] 来说，它右侧的任务要么和它没有交集，要么包含它的区间后缀\n",
    "    3. 对于当前区间来说，如果需要安排新的点，则尽量安排在后缀上\n",
    "'''\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda x:x[1])\n",
    "        run = [False] * (tasks[-1][1] + 1)\n",
    "        for s, e, d in tasks:\n",
    "            d -= sum(run[s:e+1]) # 去掉区间内运行的点个数\n",
    "            if d > 0: # 有需要安排的新的点\n",
    "                for i in range(e, s-1, -1): # 优先安排在后缀上\n",
    "                    if run[i]: # 已经有点了，跳过\n",
    "                        continue\n",
    "                    run[i] = True # 安排在后缀上\n",
    "                    d -= 1\n",
    "                    if d == 0:\n",
    "                        break\n",
    "        return sum(run)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda x:x[1])\n",
    "        run = [False] * (tasks[-1][1] + 1)\n",
    "        for s, e, d in tasks:\n",
    "            d -= sum(run[s:e+1]) # 去掉区间内运行的点个数\n",
    "            if d > 0:\n",
    "                for i in range(e, s-1, -1):\n",
    "                    if run[i]:\n",
    "                        continue\n",
    "                    run[i] = True\n",
    "                    d -= 1\n",
    "                    if d == 0:\n",
    "                        break\n",
    "        return sum(run)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda t: t[1])\n",
    "        run = [False] * (tasks[-1][1] + 1)\n",
    "        for start, end, d in tasks:\n",
    "            d -= sum(run[start:end + 1])  # 去掉运行中的时间点\n",
    "            if d > 0:\n",
    "                for i in range(end, start - 1, -1):  # 剩余的 d 填充区间后缀\n",
    "                    if run[i]:\n",
    "                         continue\n",
    "                    run[i] = True\n",
    "                    d -= 1\n",
    "                    if d == 0:\n",
    "                         break\n",
    "        return sum(run)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        # 按照任务的结束时间对任务进行排序\n",
    "        tasks.sort(key=lambda x: x[1])\n",
    "        # 创建一个布尔数组，用于记录电脑在每个时间点是否被占用\n",
    "        use = [False] * (tasks[-1][1] + 1)\n",
    "        for start, end, duration in tasks:\n",
    "            # 计算任务需要运行的时间\n",
    "            duration -= sum(use[start:end + 1])\n",
    "            if duration > 0:\n",
    "                # 从任务的结束时间开始向前遍历，找到空闲的时间点并占用\n",
    "                for t in range(end, start - 1, -1):\n",
    "                    if use[t]:continue\n",
    "                    use[t] += 1\n",
    "                    duration -= 1\n",
    "                    if duration == 0:\n",
    "                        break\n",
    "        # 返回电脑被占用的总时间\n",
    "        return sum(use)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda t: t[1])\n",
    "        run = [False] * (tasks[-1][1] + 1)\n",
    "        for start, end, d in tasks:\n",
    "            d -= sum(run[start:end + 1])  # 去掉运行中的时间点\n",
    "            if d > 0:\n",
    "                for i in range(end, start - 1, -1):  # 剩余的 d 填充区间后缀\n",
    "                    if run[i]: continue\n",
    "                    run[i] = True\n",
    "                    d -= 1\n",
    "                    if d == 0: break\n",
    "        return sum(run)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda t:t[1]) #对齐每组end位,便于找到最大长度\n",
    "        run=[False]*(tasks[-1][1]+1)\n",
    "        for s,e,d in tasks:\n",
    "            d-=sum(run[s:e+1])\n",
    "            for i in range(e,s-1,-1):\n",
    "                if d<=0: break\n",
    "                if run[i]: continue\n",
    "                run[i]=True\n",
    "                d-=1\n",
    "        return sum(run)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        # 按照end排序，run记录从0到max_end每个时间点是否在运行\n",
    "        #  对于每一个区间，尽量把运行时间放在靠后的位置，这样可以尽可能让后续的区间共用运行的时间点\n",
    "        # 每一个区间，先计算在自己的区间范围内已经有了多少运行时间\n",
    "        # 如果不够duration，再在区间靠后位置加上运行时间点\n",
    "        n=len(tasks)\n",
    "        tasks.sort(key=lambda x:x[1])\n",
    "        max_end = tasks[-1][1]\n",
    "        run = [0]*(max_end + 1)\n",
    "        total = 0\n",
    "        for i in range(n):\n",
    "            s,e,d = tasks[i]\n",
    "            finished = sum(run[s:e+1])\n",
    "            if d>finished:\n",
    "                for j in range(e, s-1, -1):\n",
    "                    if run[j]: continue\n",
    "                    run[j] = 1\n",
    "                    finished += 1\n",
    "                    total += 1\n",
    "                    if d == finished:\n",
    "                        break\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        n = len(tasks)\n",
    "        total_time = 0\n",
    "        tasks.sort(key=lambda x:x[1])\n",
    "        time_points = [0]*(tasks[-1][1]+1)\n",
    "        for s,e,d in tasks:\n",
    "            used_time = sum(time_points[s:e+1])\n",
    "            d = max(0, d-used_time)\n",
    "            total_time += d\n",
    "            i = e\n",
    "            while d > 0 and i >= s:\n",
    "                if time_points[i] == 0:\n",
    "                    d -= 1\n",
    "                    time_points[i] = 1\n",
    "                i -= 1\n",
    "        \n",
    "        return total_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, array: List[List[int]]) -> int:\n",
    "        # 按照结束时间排序\n",
    "        array.sort(key=lambda x: x[1])\n",
    "        # 最大结束时间\n",
    "        most = array[-1][1] + 1\n",
    "        # 记录该日期是否被使用\n",
    "        cal = [0 for _ in range(most)]\n",
    "        for start, end, period in array:\n",
    "            period -= sum(cal[start:end+1])\n",
    "            if period > 0:\n",
    "                for i in range(end, start - 1, -1):\n",
    "                    if cal[i]:\n",
    "                        continue\n",
    "                    cal[i] = 1\n",
    "                    period -= 1\n",
    "\n",
    "                    if not period:\n",
    "                        break\n",
    "        total = sum(cal)\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda t: t[1])\n",
    "        run = [False] * (tasks[-1][1] + 1)\n",
    "        for start, end, d in tasks:\n",
    "            d -= sum(run[start:end + 1])  # 去掉运行中的时间点\n",
    "            if d > 0:\n",
    "                for i in range(end, start - 1, -1):  # 剩余的 d 填充区间后缀\n",
    "                    if run[i]: continue\n",
    "                    run[i] = True\n",
    "                    d -= 1\n",
    "                    if d == 0: break\n",
    "        return sum(run)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda x:x[1])\n",
    "        run = [False] * (tasks[-1][1] + 1)\n",
    "        ans = 0\n",
    "        for l, r, t in tasks:\n",
    "            t -= sum(run[l:r + 1])\n",
    "            if t > 0:\n",
    "                for i in range(r, l - 1, -1):\n",
    "                    if not run[i]:\n",
    "                        run[i] = True\n",
    "                        t -= 1\n",
    "                        ans += 1\n",
    "                    if t <= 0:\n",
    "                        break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda t: t[1])\n",
    "        st = [(-2, -2, 0)]  # 闭区间左右端点，栈底到栈顶的区间长度的和\n",
    "        for start, end, d in tasks:\n",
    "            _, r, s = st[bisect_left(st, (start,)) - 1]\n",
    "            d -= st[-1][2] - s  # 去掉运行中的时间点\n",
    "            if start <= r:  # start 在区间 st[i] 内\n",
    "                d -= r - start + 1  # 去掉运行中的时间点\n",
    "            if d <= 0: continue\n",
    "            while end - st[-1][1] <= d:  # 剩余的 d 填充区间后缀\n",
    "                l, r, _ = st.pop()\n",
    "                d += r - l + 1  # 合并区间\n",
    "            st.append((end - d + 1, end, st[-1][2] + d))\n",
    "        return st[-1][2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda t: t[1])\n",
    "        run = [False] * (tasks[-1][1] + 1)\n",
    "        for start, end, d in tasks:\n",
    "            d -= sum(run[start:end + 1])  # 去掉运行中的时间点\n",
    "            if d > 0:\n",
    "                for i in range(end, start - 1, -1):  # 剩余的 d 填充区间后缀\n",
    "                    if run[i]: continue\n",
    "                    run[i] = True\n",
    "                    d -= 1\n",
    "                    if d == 0: break\n",
    "        return sum(run)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda t: t[1])\n",
    "        run = [False] * (tasks[-1][1] + 1)\n",
    "        for start, end, d in tasks:\n",
    "            d -= sum(run[start:end + 1])  # 去掉运行中的时间点\n",
    "            if d > 0:\n",
    "                for i in range(end, start - 1, -1):  # 剩余的 d 填充区间后缀\n",
    "                    if run[i]: continue\n",
    "                    run[i] = True\n",
    "                    d -= 1\n",
    "                    if d == 0: break\n",
    "        return sum(run)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda t: t[1])\n",
    "        judge = [0] * (tasks[-1][1] + 1)  # 判断某一时间是否是重叠时间\n",
    "        for start, end, long in tasks:\n",
    "            long = long - sum(judge[start:end + 1])\n",
    "            if long > 0:\n",
    "                for i in range(end, start - 1, -1):\n",
    "                    if judge[i] == 1: continue\n",
    "                    judge[i] = 1\n",
    "                    long = long - 1\n",
    "                    if long == 0: break\n",
    "        return sum(judge)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import *\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda t:t[1])\n",
    "        st=[(-2,-2,0)]\n",
    "        for start, end, d in tasks:\n",
    "            _, r, s = st[bisect_left(st,(start,))-1]\n",
    "            d -= st[-1][2] - s\n",
    "            if r >= start:\n",
    "                d -= r - start + 1\n",
    "            if d <=0: continue\n",
    "            while end - st[-1][1] <= d:\n",
    "                nl,nr,_=st.pop()\n",
    "                d += nr - nl + 1\n",
    "            st.append((end - d + 1, end, st[-1][2] + d))\n",
    "        return st[-1][2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda x: x[1])\n",
    "        n = len(tasks)\n",
    "        runtime = [0] * 2001\n",
    "        res = 0\n",
    "        for s, e, d in tasks:\n",
    "            if (d0 := sum(runtime[s:e + 1])) >= d:\n",
    "                continue\n",
    "            else:\n",
    "                d -= d0\n",
    "                for i in range(e, s-1, -1):\n",
    "                    if not runtime[i]:\n",
    "                        runtime[i] = 1\n",
    "                        d -= 1\n",
    "                    if not d:\n",
    "                        break\n",
    "        return sum(runtime)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort()\n",
    "        max_end = max([e for _, e, _ in tasks])\n",
    "        ans = 0\n",
    "        h = []\n",
    "        p = 0\n",
    "        for i in range(max_end+1) :\n",
    "            while p < len(tasks) and tasks[p][0] == i :\n",
    "                heappush(h, (tasks[p][1], tasks[p][0], tasks[p][2]))\n",
    "                p += 1\n",
    "            \n",
    "            while h and h[0][0] == i :\n",
    "                end_i, start_i, dur_i = heappop(h)\n",
    "                ans += dur_i\n",
    "                for j in range(len(h)) :\n",
    "                    res = max(h[j][2] - min(i+1-h[j][1], dur_i), 0)\n",
    "                    cost = h[j][2] - res\n",
    "                    h[j] = (h[j][0], h[j][1] + cost, res)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        n = len(tasks)\n",
    "        tasks.sort(key = lambda x: x[1])\n",
    "        # 从右往左\n",
    "        s = set()\n",
    "        for i in range(n):\n",
    "            start, end, duration = tasks[i]\n",
    "            if i == 0:\n",
    "                for j in range(end, end - duration, -1):\n",
    "                    s.add(j)\n",
    "            else:\n",
    "                cur = 0\n",
    "                for j in range(start, end + 1):\n",
    "                    if j in s:\n",
    "                        cur += 1\n",
    "                if cur >= duration:\n",
    "                    continue\n",
    "                else:\n",
    "                    rest = duration - cur\n",
    "                    tmp = 0\n",
    "                    for j in range(end, start - 1, -1):\n",
    "                        if j not in s:\n",
    "                            s.add(j)\n",
    "                            tmp += 1\n",
    "                        if tmp == rest:\n",
    "                            break\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        n = len(tasks) \n",
    "        tasks.sort(key = lambda x : x[1]) \n",
    "        run = [False] * (tasks[-1][1] + 1) \n",
    "        for start, end, d in tasks : \n",
    "            d -= sum(run[start:end + 1]) \n",
    "            if d > 0 : \n",
    "                for i in range(end, start - 1, -1) : \n",
    "                    if run[i] : continue \n",
    "                    run[i] = True \n",
    "                    d -= 1 \n",
    "                    if d == 0 : break \n",
    "        return sum(run)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda x: x[1])\n",
    "        ans = 0\n",
    "        vis = [False] * 20001\n",
    "        for (l, r, d) in tasks:\n",
    "            for i in range(l, r + 1):\n",
    "                if vis[i]:\n",
    "                    d -= 1\n",
    "            i = r\n",
    "            while d > 0:\n",
    "                if not vis[i]:\n",
    "                    vis[i] = True\n",
    "                    d -= 1\n",
    "                    ans += 1\n",
    "                i -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect \n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda x : x[1])\n",
    "        stack = []\n",
    "        for [s, e, d] in tasks:\n",
    "            assert e-s+1 >= d\n",
    "            assert d > 0\n",
    "            if len(stack) == 0:\n",
    "                stack.append([e-d+1, e, d])\n",
    "            else:\n",
    "                ind = bisect.bisect(stack, [s, 0, 0])\n",
    "                # stack[ind][0] >= s \n",
    "                # ind = 0 or stack[ind-1][0] < s\n",
    "                if ind == 0:\n",
    "                    d -= stack[-1][-1] \n",
    "                else:\n",
    "                    d -= stack[-1][-1] - stack[ind-1][-1]\n",
    "                    if stack[ind-1][1] >= s:\n",
    "                        d -= stack[ind-1][1] - s + 1 \n",
    "                if d <= 0:\n",
    "                    continue \n",
    "                while len(stack) > 0 and d >= e - stack[-1][1]:\n",
    "                    [s_, e_, d_] = stack.pop()\n",
    "                    d += e_ - s_ + 1 \n",
    "                if len(stack) == 0:\n",
    "                    d_ = d \n",
    "                else:\n",
    "                    d_ = d + stack[-1][-1]\n",
    "                stack.append([e-d+1, e, d_])\n",
    "        return stack[-1][-1]\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key = lambda x : x[1])\n",
    "        n = len(tasks)\n",
    "        vis = [0] * (tasks[n-1][1] + 1)\n",
    "        for start,end,d in tasks:\n",
    "            d -= sum(vis[start:end+1])\n",
    "            if d > 0:\n",
    "                for i in range(end,start-1,-1):\n",
    "                    if vis[i] == 0:\n",
    "                        vis[i]  = 1\n",
    "                        d -= 1\n",
    "                        if d == 0:\n",
    "                            break\n",
    "        return sum(vis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        n=len(tasks)\n",
    "        tasks.sort(key=lambda x:x[1])\n",
    "        max_end = tasks[-1][1]\n",
    "        run = [0]*(max_end + 1)\n",
    "        total = 0\n",
    "        for i in range(n):\n",
    "            s,e,d = tasks[i]\n",
    "            finished = sum(run[s:e+1])\n",
    "            if d>finished:\n",
    "                for j in range(e, s-1, -1):\n",
    "                    if run[j]: continue\n",
    "                    run[j] = 1\n",
    "                    finished += 1\n",
    "                    total += 1\n",
    "                    if d == finished:\n",
    "                        break\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda t: t[1])\n",
    "        run = [False] * (tasks[-1][1] + 1)\n",
    "        for start, end, d in tasks:\n",
    "            d -= sum(run[start:end + 1])  # 去掉运行中的时间点\n",
    "            if d > 0:\n",
    "                for i in range(end, start - 1, -1):  # 剩余的 d 填充区间后缀\n",
    "                    if run[i]: \n",
    "                        continue\n",
    "                    run[i] = True\n",
    "                    d -= 1\n",
    "                    if d == 0: \n",
    "                        break\n",
    "        return sum(run)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks = sorted(tasks, key=lambda i:i[1])\n",
    "        res = [0] * 2001\n",
    "        for s, e, t in tasks:\n",
    "            cur = sum(res[ii] for ii in range(s, e + 1))\n",
    "            if cur >= t:\n",
    "                continue\n",
    "            cur = t - cur\n",
    "            for ii in range(e, s - 1, -1):\n",
    "                if res[ii] == 0:\n",
    "                    res[ii] = 1\n",
    "                    cur -= 1\n",
    "                if cur == 0:\n",
    "                    break\n",
    "        return sum(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda x: x[1])\n",
    "        s = [False] * 2001\n",
    "        for l, r, d in tasks:\n",
    "            d -= sum(s[l:r + 1])\n",
    "            if d > 0:\n",
    "                for i in range(r, l - 1, -1):\n",
    "                    if not s[i]:\n",
    "                        s[i] = True\n",
    "                        d -= 1\n",
    "                    if d <= 0:\n",
    "                        break\n",
    "        return sum(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappush, heappop\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort()\n",
    "        j = 0\n",
    "        heap = []\n",
    "        start_delta = 0\n",
    "        ans = 0\n",
    "        while j < len(tasks) or heap:\n",
    "            if heap:\n",
    "                htop = heap[0][0] + start_delta\n",
    "            else:\n",
    "                htop = 1000000000\n",
    "            if j < len(tasks):\n",
    "                ttop = tasks[j][0]\n",
    "            else:\n",
    "                ttop = 1000000000\n",
    "            if ttop <= htop:\n",
    "                heappush(heap, (tasks[j][1] + 1 - tasks[j][2] - start_delta, tasks[j][1]))\n",
    "                j += 1\n",
    "            else:\n",
    "                s, e = heap[0]\n",
    "                if s + start_delta <= e:\n",
    "                    if ttop <= e:\n",
    "                        dur = ttop - (s + start_delta)\n",
    "                        start_delta += dur\n",
    "                        ans += dur\n",
    "                    else:\n",
    "                        heappop(heap)\n",
    "                        dur = e - (s + start_delta) + 1\n",
    "                        start_delta += dur\n",
    "                        ans += dur\n",
    "                else:\n",
    "                    heappop(heap)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: list[list[int]]) -> int:\n",
    "        max_time = max([task[1] for task in tasks])\n",
    "        tasks.sort(key = lambda x: x[1])\n",
    "        tot = 0\n",
    "        used = [0] * (max_time + 1)\n",
    "        for curr_task in tasks:\n",
    "            s, e, d = curr_task\n",
    "            up = sum(used[s:e+1])\n",
    "            remain = d - up\n",
    "            if remain <= 0:\n",
    "                continue\n",
    "            else:\n",
    "                for i in range(remain):\n",
    "                    while(used[e - i] == 1):\n",
    "                        e -= 1\n",
    "                    used[e-i] = 1\n",
    "        return sum(used)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        n = len(tasks)\n",
    "        # 在重合的地方多练!\n",
    "        tasks.sort(key = lambda x: x[1])\n",
    "        # 从右往左\n",
    "        ss = set()\n",
    "        for i in range(n):\n",
    "            start, end, duration = tasks[i]\n",
    "            if i == 0:\n",
    "                for j in range(end, end - duration, -1):\n",
    "                    ss.add(j)\n",
    "            else:\n",
    "                cur = 0\n",
    "                for j in range(start, end + 1):\n",
    "                    if j in ss:\n",
    "                        cur += 1\n",
    "                if cur >= duration:\n",
    "                    continue\n",
    "                else:\n",
    "                    rest = duration - cur\n",
    "                    tmp = 0\n",
    "                    for j in range(end, start - 1, -1):\n",
    "                        if j not in ss:\n",
    "                            ss.add(j)\n",
    "                            tmp += 1\n",
    "                        if tmp == rest:\n",
    "                            break\n",
    "        return len(ss)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda t: t[1])\n",
    "        run = [False] * (tasks[-1][1] + 1)\n",
    "        for start, end, d in tasks:\n",
    "            d -= sum(run[start:end + 1])  # 去掉运行中的时间点\n",
    "            if d > 0:\n",
    "                for i in range(end, start - 1, -1):  # 剩余的 d 填充区间后缀\n",
    "                    if run[i]: continue\n",
    "                    run[i] = True\n",
    "                    d -= 1\n",
    "                    if d == 0: break\n",
    "        return sum(run)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        # 首先根据任务的结束时间进行排序\n",
    "        tasks.sort(key=lambda t: t[1])\n",
    "        \n",
    "        # 创建一个运行时间数组，记录哪些时间点是运行状态\n",
    "        run = [False] * (tasks[-1][1] + 1)\n",
    "        \n",
    "        # 遍历每一个任务\n",
    "        for start, end, d in tasks:\n",
    "            # 计算任务在给定时间区间内已经有多少时间点是运行状态\n",
    "            d -= sum(run[start:end + 1])\n",
    "            \n",
    "            # 如果任务所需的运行时间点还未满足\n",
    "            if d > 0:\n",
    "                # 从任务的结束时间向开始时间方向，选择未运行的时间点为其运行\n",
    "                for i in range(end, start - 1, -1):\n",
    "                    if run[i]: continue\n",
    "                    run[i] = True\n",
    "                    d -= 1\n",
    "                    if d == 0: break\n",
    "        \n",
    "        # 返回电脑需要运行的最少秒数\n",
    "        return sum(run)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda x:x[1])\n",
    "        run=[False]*(tasks[-1][1]+1)\n",
    "        for start,end,d in tasks:\n",
    "            d-=sum(run[start:end+1])\n",
    "            while d>0:\n",
    "                for i in range(end,start-1,-1):\n",
    "                    if not run[i]:\n",
    "                        run[i]=True\n",
    "                        d-=1\n",
    "                        if d==0:\n",
    "                            break\n",
    "        return sum(run)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, t: List[List[int]]) -> int:\n",
    "        t.sort(key=lambda x: x[1])\n",
    "        s = []\n",
    "        ans = 0 \n",
    "        pre = {-1: 0}\n",
    "        for st, end, d in t:\n",
    "            if (not s) or (s[-1][1]<st):\n",
    "                s.append([end-d+1, end]) \n",
    "                ans += d\n",
    "                pre[len(s) - 1] = pre[len(s) - 2] + d \n",
    "            else:\n",
    "                i =  bisect_left(s, [st])\n",
    "                res = pre[len(s) - 1] - pre[i - 1]\n",
    "                if i>0:\n",
    "                    if s[i -1][1]<st:\n",
    "                        pass \n",
    "                    else:\n",
    "                        d -= (s[i -1][1] - st + 1)\n",
    "                        st = s[i - 1][1] + 1 \n",
    "                if res>=d:\n",
    "                    pass \n",
    "                else:\n",
    "                    j = len(s) - 1 \n",
    "                    while s:\n",
    "                        if (pre[j] - pre[i-1] + (end - s[-1][1]))<d:\n",
    "                            del pre[j]\n",
    "                            tmp = s.pop()\n",
    "                            ans -= (tmp[1] - tmp[0] + 1) \n",
    "                            j -= 1 \n",
    "                        else:\n",
    "                            break \n",
    "                    newD = d - (pre[j] - pre[i - 1])\n",
    "                    s.append([end-newD+1, end]) \n",
    "                    ans += newD\n",
    "                    pre[len(s) - 1] = pre[len(s) - 2] + newD \n",
    "        return ans \n",
    "                    \n",
    "\n",
    "               \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda t: t[1])\n",
    "        run = [False] * (tasks[-1][1] + 1)\n",
    "        for start, end, d in tasks:\n",
    "            d -= sum(run[start:end + 1])  # 去掉运行中的时间点\n",
    "            if d > 0:\n",
    "                for i in range(end, start - 1, -1):  # 剩余的 d 填充区间后缀\n",
    "                    if run[i]: continue\n",
    "                    run[i] = True\n",
    "                    d -= 1\n",
    "                    if d == 0: break\n",
    "        return sum(run)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        n = len(tasks)\n",
    "        tasks.sort(key=lambda x: (x[1], -x[2]))\n",
    "        \n",
    "        # cnt = 0\n",
    "        last = -1\n",
    "        run = [0] * (2001)\n",
    "        res = 0\n",
    "        # print(tasks)\n",
    "        for s, e, d in tasks:\n",
    "            cnt = 0\n",
    "            for i in range(last, s - 1, -1):\n",
    "                if run[i] == 1:\n",
    "                    cnt += 1\n",
    "            if cnt < d:           \n",
    "                for i in range(e, s - 1, -1):\n",
    "                    # print(i, cnt, e, s, d)\n",
    "                    if run[i] == 1:\n",
    "                        continue\n",
    "                    else:\n",
    "                        run[i] = 1\n",
    "                        cnt += 1\n",
    "                    if cnt == d:\n",
    "                        break\n",
    "            last = e\n",
    "        # print(run)\n",
    "        return sum(run)\n",
    "        \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks = sorted(tasks, key=lambda x:x[1])\n",
    "        time = set()\n",
    "\n",
    "        for s, e, duration in tasks:\n",
    "            for t in time:\n",
    "                if s <= t <= e:\n",
    "                    duration -= 1\n",
    "                if duration == 0:\n",
    "                    break\n",
    "        \n",
    "            while duration > 0:\n",
    "                if e not in time:\n",
    "                    time.add(e)\n",
    "                    duration -= 1\n",
    "                e-=1\n",
    "        return len(time)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinimumTime(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda t: t[1])\n",
    "        u = tasks[-1][1]\n",
    "        cnt = [0] * (4 * u)\n",
    "        todo = [False] * (4 * u)\n",
    "\n",
    "        def do(o: int, l: int, r: int) -> None:\n",
    "            cnt[o] = r - l + 1\n",
    "            todo[o] = True\n",
    "\n",
    "        def spread(o: int, l: int, m: int, r: int) -> None:\n",
    "            if todo[o]:\n",
    "                todo[o] = False\n",
    "                do(o * 2, l, m)\n",
    "                do(o * 2 + 1, m + 1, r)\n",
    "\n",
    "        # 查询区间正在运行的时间点 [L,R]   o,l,r=1,1,u\n",
    "        def query(o: int, l: int, r: int, L: int, R: int) -> int:\n",
    "            if L <= l and r <= R: return cnt[o]\n",
    "            m = (l + r) // 2\n",
    "            spread(o, l, m, r)\n",
    "            if m >= R: return query(o * 2, l, m, L, R)\n",
    "            if m < L: return query(o * 2 + 1, m + 1, r, L, R)\n",
    "            return query(o * 2, l, m, L, R) + query(o * 2 + 1, m + 1, r, L, R)\n",
    "\n",
    "        # 在区间 [L,R] 的后缀上新增 suffix 个时间点    o,l,r=1,1,u\n",
    "        # 相当于把线段树二分和线段树更新合并成了一个函数，时间复杂度为 O(log u)\n",
    "        def update(o: int, l: int, r: int, L: int, R: int) -> None:\n",
    "            size = r - l + 1\n",
    "            if cnt[o] == size: return  # 全部为运行中\n",
    "            nonlocal suffix\n",
    "            if L <= l and r <= R and size - cnt[o] <= suffix:  # 整个区间全部改为运行中\n",
    "                suffix -= size - cnt[o]\n",
    "                do(o, l, r)\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            spread(o, l, m, r)\n",
    "            if m < R: update(o * 2 + 1, m + 1, r, L, R)  # 先更新右子树\n",
    "            if suffix: update(o * 2, l, m, L, R)  # 再更新左子树（如果还有需要新增的时间点）\n",
    "            cnt[o] = cnt[o * 2] + cnt[o * 2 + 1]\n",
    "\n",
    "        for start, end, d in tasks:\n",
    "            suffix = d - query(1, 1, u, start, end)  # 去掉运行中的时间点\n",
    "            if suffix > 0: update(1, 1, u, start, end)  # 新增时间点\n",
    "        return cnt[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "sg = [0] * 8000\r\n",
    "lz = [False] * 8000\r\n",
    "def build(id: int, l: int, r: int) -> None:\r\n",
    "    sg[id] = 0\r\n",
    "    lz[id] = False\r\n",
    "    if r > l:\r\n",
    "        nxt = id << 1\r\n",
    "        mid = l + r >> 1\r\n",
    "        build(nxt, l, mid)\r\n",
    "        build(nxt | 1, mid + 1, r)\r\n",
    "\r\n",
    "def query(id: int, l: int, r: int, left: int, right: int) -> int:\r\n",
    "    nxt = id << 1\r\n",
    "    mid = l + r >> 1\r\n",
    "    if lz[id]:\r\n",
    "        sg[id] = r - l + 1\r\n",
    "        if r > l:\r\n",
    "            lz[nxt] = lz[nxt | 1] = True\r\n",
    "        lz[id] = False\r\n",
    "\r\n",
    "    if left <= l and right >= r:\r\n",
    "        return sg[id]\r\n",
    "    if l > right or r < left:\r\n",
    "        return 0\r\n",
    "\r\n",
    "    return query(nxt, l, mid, left, right) + query(nxt | 1, mid + 1, r, left, right)\r\n",
    "\r\n",
    "def update(id: int, l: int, r: int, left: int, right: int) -> None:\r\n",
    "    nxt = id << 1\r\n",
    "    mid = l + r >> 1\r\n",
    "    if left <= l and right >= r:\r\n",
    "        sg[id] = r - l + 1\r\n",
    "        if r > l:\r\n",
    "            lz[nxt] = lz[nxt | 1] = True\r\n",
    "        return\r\n",
    "    if l > right or r < left:\r\n",
    "        return\r\n",
    "    update(nxt, l, mid, left, right)\r\n",
    "    update(nxt | 1, mid + 1, r, left, right)\r\n",
    "    sg[id] = sg[nxt] + sg[nxt | 1]\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def findMinimumTime(self, tasks: list[list[int]]) -> int:\r\n",
    "        tasks.sort(key=lambda t: t[1])\r\n",
    "        n = tasks[-1][1]\r\n",
    "        build(1, 0, n)\r\n",
    "        for s, e, d in tasks:\r\n",
    "            gap = d - query(1, 0, n, s, e)\r\n",
    "            if gap <= 0: continue\r\n",
    "            lo = s\r\n",
    "            hi = e\r\n",
    "            while lo < hi:\r\n",
    "                mid = 1 + (lo + hi >> 1)\r\n",
    "                if (e - mid + 1 - query(1, 0, n, mid, e) >= gap):\r\n",
    "                    lo = mid\r\n",
    "                else:\r\n",
    "                    hi = mid - 1\r\n",
    "            update(1, 0, n, lo, e)\r\n",
    "        \r\n",
    "        return sg[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "sg = [0] * 8000\r\n",
    "lz = [0] * 8000\r\n",
    "def build(id: int, l: int, r: int) -> None:\r\n",
    "    sg[id] = 0\r\n",
    "    lz[id] = 0\r\n",
    "    if r > l:\r\n",
    "        nxt = id << 1\r\n",
    "        mid = l + r >> 1\r\n",
    "        build(nxt, l, mid)\r\n",
    "        build(nxt | 1, mid + 1, r)\r\n",
    "\r\n",
    "def push_down(id: int, l: int, r: int) -> None:\r\n",
    "    sg[id] += lz[id]\r\n",
    "    if r > l:\r\n",
    "        nxt = id << 1\r\n",
    "        mid = l + r >> 1\r\n",
    "        rmax = r - mid - sg[nxt | 1] - lz[nxt | 1]\r\n",
    "        if rmax >= lz[id]:\r\n",
    "            lz[nxt | 1] += lz[id]\r\n",
    "        else:\r\n",
    "            lz[nxt] += lz[id] - rmax\r\n",
    "            lz[nxt | 1] += rmax\r\n",
    "    lz[id] = 0\r\n",
    "\r\n",
    "def query(id: int, l: int, r: int, left: int, right: int) -> int:\r\n",
    "    if lz[id] > 0:\r\n",
    "        push_down(id, l, r)\r\n",
    "    \r\n",
    "    if left <= l and right >= r:\r\n",
    "        return sg[id]\r\n",
    "\r\n",
    "    if sg[id] == 0 or left > r or right < l:\r\n",
    "        return 0\r\n",
    "    \r\n",
    "    nxt = id << 1\r\n",
    "    mid = l + r >> 1\r\n",
    "    ret = query(nxt, l, mid, left, right) + query(nxt | 1, mid + 1, r, left, right)\r\n",
    "    sg[id] = sg[nxt] + sg[nxt | 1]\r\n",
    "    return ret\r\n",
    "\r\n",
    "# add val points as close to right as possible, return added points\r\n",
    "def update(id: int, l: int, r: int, right: int, val: int) -> None:\r\n",
    "    if lz[id] > 0:\r\n",
    "        push_down(id, l, r)\r\n",
    "    \r\n",
    "    if right < l:\r\n",
    "        return 0\r\n",
    "\r\n",
    "    if right >= r:\r\n",
    "        val = min(val, r - l + 1 - sg[id])\r\n",
    "        if val > 0:\r\n",
    "            lz[id] += val\r\n",
    "            push_down(id, l, r)\r\n",
    "        return val\r\n",
    "\r\n",
    "    nxt = id << 1\r\n",
    "    mid = l + r >> 1\r\n",
    "    ret = 0\r\n",
    "    if right > mid:\r\n",
    "        ret += update(nxt | 1, mid + 1, r, right, val)\r\n",
    "    if val > ret:\r\n",
    "        ret += update(nxt, l, mid, right, val - ret)\r\n",
    "    sg[id] = sg[nxt] + sg[nxt | 1]\r\n",
    "    return ret\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def findMinimumTime(self, tasks: list[list[int]]) -> int:\r\n",
    "        tasks.sort(key=lambda t: t[1])\r\n",
    "        n = tasks[-1][1]\r\n",
    "        build(1, 0, n)\r\n",
    "        for s, e, d in tasks:\r\n",
    "            d -= query(1, 0, n, s, e)\r\n",
    "            if d > 0:\r\n",
    "                update(1, 0, n, e, d)\r\n",
    "        \r\n",
    "        return sg[1] + lz[1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
